package 力扣;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yyq
 * @create 2022-04-26 14:22
 */
public class leetcode216 {
    public static void main(String[] args) {
        leetcode216 yyq=new leetcode216();
        yyq.combinationSum3(3,9);
    }
    int sum=0;
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> lists=new ArrayList<>();
        List<Integer> list = new ArrayList<>();

        for (int i = 1; i <= k; i++) {
            sum = sum + i;
            list.add(i);
        }
        if(sum>n) return lists;
        if(sum==n) {
            lists.add(list);
            return lists;
        }
        list.clear();
        sum = 0;

        for (int i = 9;i>=k;i--){
            sum = sum + i;
            list.add(i);
        }
        if(sum<n) return lists;
        if(sum==n){
            lists.add(list);
            return lists;
        }
        list.clear();
        sum = 0;

        int startIndex = 1;
        backTrack(list,lists,k,n,startIndex);
        return lists;
    }

    private void backTrack(List<Integer> list, List<List<Integer>> lists, int k, int n,int startIndex) {
        // 剪支操作 这个剪支是减去其下方的支
        if(sum>n) return;
        if(list.size()==k){
            if(sum == n){
                lists.add(new ArrayList<>(list));
            }
            return;
        }
        for (int i= startIndex;i < 10;i++){
            list.add(i);
            sum = sum + i;
            // 这个剪支是减去右方的树枝
            if(sum<=n){
                backTrack(list,lists,k,n,i+1);
                list.remove(list.size()-1);
                sum = sum -i;
            }
            else {
                list.remove(list.size()-1);
                sum = sum -i;
                return;
            }
        }
    }
}
